import java.util.*;

public class EquationTree{
	
	protected EquationNode root;
	
	final static String[] operators={"+","-","*","/","^"};
	
	public EquationTree(){
		root = null;
	}
	
	public EquationTree(int numOperands){
		//Constructor creates a random tree with the specified number of operands
		ArrayList<EquationNode> newNodeList = new ArrayList<EquationNode>();
		Random rand = new Random();
		
		String newOperand = operators[rand.nextInt(operators.length)];
		String newNumber = String.valueOf(rand.nextInt(10) + 1);
		String newNumber1 = String.valueOf(rand.nextInt(10) + 1);
		EquationNode newNode = new EquationNode(newOperand, newNumber, newNumber1);
		newNodeList.add(newNode);	//add the newNode to the list
		
		//Randomly create numOperands nodes.
		for(int i = 1; i < numOperands; i ++){
			newOperand = operators[rand.nextInt(operators.length)];
			newNumber = String.valueOf(rand.nextInt(10) + 1);
			
			if(rand.nextInt(100)%2 == 0)//insert newNumber at the left child
				newNode = new EquationNode(newOperand, newNumber, null);
			else						//insert newNumber at the right child
				newNode = new EquationNode(newOperand, null, newNumber);
			
			newNodeList.add(newNode);	//add the newNode to the list
		}
		
		root = newNodeList.get(0);		//set this.root node to the zeroth index.
		
		//randomly insert the remaining nodes
		for(int i = 1; i < numOperands; i ++){
			insertNode(newNodeList.get(i), this, rand.nextInt(i), rand.nextInt((int)Math.pow(2,i)));
		}
	}
	
	public EquationTree(int numOperands, Team team){
		//Constructor creates a random tree with the specified number of operands
		ArrayList<EquationNode> newNodeList = new ArrayList<EquationNode>();
		Random rand = new Random();
		String newNumber, newNumber1;
		
		//create the root node. This is done outside the for loop, b/c it has no null children
		String newOperand = operators[rand.nextInt(operators.length)];
		if(rand.nextInt(100)%2 == 0)	//create a constant
			newNumber = String.valueOf(rand.nextInt(10) + 1);
		else							//create a variable from team statlist
			newNumber = team.getRandomStat();
		
		if(rand.nextInt(100)%2 == 0)	//create a constant
			newNumber1 = String.valueOf(rand.nextInt(10) + 1);
		else							//create a variable from team statlist
			newNumber1 = team.getRandomStat();
		
		EquationNode newNode = new EquationNode(newOperand, newNumber, newNumber1);
		newNodeList.add(newNode);	//add the newNode to the list
		
		//Randomly create numOperands-1 nodes.
		for(int i = 1; i < numOperands; i ++){
			newOperand = operators[rand.nextInt(operators.length)];

			if(rand.nextInt(100)%2 == 0)	//create a constant
				newNumber = String.valueOf(rand.nextInt(10) + 1);
			else							//create a variable from team statlist
				newNumber = team.getRandomStat();
			
			if(rand.nextInt(100)%2 == 0)//insert newNumber at the left child
				newNode = new EquationNode(newOperand, newNumber, null);
			else						//insert newNumber at the right child
				newNode = new EquationNode(newOperand, null, newNumber);
			
			newNodeList.add(newNode);	//add the newNode to the list
		}
		
		root = newNodeList.get(0);		//set this.root node to the zeroth index.
		
		//randomly insert the remaining nodes
		for(int i = 1; i < numOperands; i ++){
			insertNode(newNodeList.get(i), this, rand.nextInt(i), rand.nextInt((int)Math.pow(2,i)));
		}
	}
	
	/**
	 * Inserts a node in a tree at the specified depth, and specified number of nodes starting from the far left of the tree.
	 * If depth or nodesToRight is to large, the max depth and max nodes to the right will be used.
	 *   
	 * @param insertNode	the node to be inserted.
	 * @param inThisTree	the tree in which insertNode will be inserted.
	 * @param treeDepth		the depth the node will be inserted at.
	 * @param nodesToRight	number of nodes from left to right starting at treeDepth. 
	 */
	public void insertNode(EquationNode insertNode, EquationTree inThisTree, int treeDepth, int nodesToRight){
		EquationNode curNode = inThisTree.root;
		int traversedRight = 0;
		boolean foundInsertionNode = false;
		
		while(!foundInsertionNode){
			if( Math.pow(2, treeDepth - 1) > nodesToRight ){
				//go left
				treeDepth -= 1;
				
				if(curNode.leftChild != null)
					curNode = curNode.leftChild;
				else
					foundInsertionNode = true;
			}
			else{
				//go right
				treeDepth -= 1;
				traversedRight = (int) Math.pow(2, treeDepth);
				nodesToRight -= traversedRight;
				
				if(curNode.rightChild != null)
					curNode = curNode.rightChild;
				else
					foundInsertionNode = true;
			}
			
			if(treeDepth == 0)
				foundInsertionNode = true;
		}
		
		//insert the node at curNode
		EquationNode tempNode = new EquationNode(curNode);
		//curNode = insertNode;
		curNode.setItem(insertNode.item);
		curNode.leftChild = insertNode.leftChild;
		curNode.rightChild = insertNode.rightChild;
		
		if(curNode.leftChild == null)
			curNode.leftChild = new EquationNode(tempNode);
		else
			curNode.rightChild = new EquationNode(tempNode);
	}
	
	public void setRoot(EquationNode newRoot){
		root = newRoot;
	}
	
	/**
	 * Returns the computation of this equation.
	 * 
	 * @param team	the team to pull stats from.
	 * @return	the computation of this equation, for team
	 */
	public Double compute(Team team){
		return compute(root, team);
	}
	private Double compute(EquationNode root, Team team){
		String item = root.item;
		Double returnVal;
		
		try{
			returnVal = Double.valueOf(item);
			
			return returnVal;	//item was double, therefore return its value;
		}catch(NumberFormatException nfe){
			//item was not a double check if it's an operand
			if(isOperand(item)){
				//item is an operand find which one and do the appropriate calculation
				if(item.equals("+"))
					return compute(root.leftChild, team) + compute(root.rightChild, team);
				else if(item.equals("-"))
					return compute(root.leftChild, team) - compute(root.rightChild, team);
				else if(item.equals("*"))
					return compute(root.leftChild, team) * compute(root.rightChild, team);
				else if(item.equals("/"))
					return compute(root.leftChild, team) / compute(root.rightChild, team);
				else if(item.equals("^"))
					return Math.pow(compute(root.leftChild, team),  compute(root.rightChild, team));
				
				//Current list of operators: "+","-","*","/","^"
			}
			else{
				//item must be a stat.
				returnVal = team.getStat(item);
				
				return returnVal;
			}
			
		}
		
		return 0.0;
	}
	
	private boolean isOperand(String str){
		int index = 0;
		
		while(index < operators.length){
			if(str.equals(operators[index ++]))
				return true;
		}
		
		return false;
	}
	
	public void displayInorder(){
		inorder(root);
	}
	private void inorder(EquationNode eq){
		if(eq != null){
			System.out.print("(");
			inorder(eq.leftChild);
			System.out.print(eq.item);
			inorder(eq.rightChild);
			System.out.print(")");
		}
	}

	public void displayPreorder(){
		preorder(root);
	}
	private void preorder(EquationNode root){
		if(root != null){
			System.out.print(root.item);
			preorder(root.leftChild);
			preorder(root.rightChild);
		}
	}
}